// 给定一个整数数组 nums，其中恰好有两个元素只出现一次，其余所有元素均出现两次。 找出只出现一次的那两个元素。

// 示例 :

// 输入: [1,2,1,3,2,5]
// 输出: [3,5]
// 注意：

// 结果输出的顺序并不重要，对于上面的例子， [5, 3] 也是正确答案。
// 你的算法应该具有线性时间复杂度。你能否仅使用常数空间复杂度来实现？

#include "../stdc++.h"

// 不相同的两个数字分别在两个小数组中
// 首先我们先把原数组全部异或起来，那么我们会得到一个数字，这个数字是两个不相同的数字异或的结果
// 取出其中任意一位为 ‘1’ 的位
// 用 a &= -a 来取出最右端为 ‘1’ 的位

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int diff = accumulate(nums.begin(), nums.end(), 0, bit_xor<int>());
        diff &= -diff; // 找出从右往左第一个不同的1
        vector<int> res(2, 0);
        for (int &num : nums) {
            if (num & diff) res[0] ^= num;
            else res[1] ^= num;
        }
        return res;
    }
};

// 集合
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        unordered_set<int> hashSet{};
        for (int& num : nums) {
            if (hashSet.count(num) > 0) {
                hashSet.erase(num);
            } else {
                hashSet.insert(num);
            }
        }
        vector<int> res(hashSet.begin(), hashSet.end());
        return res;
    }
};

// 位运算
class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int x_or_sum{0};
        for (int& num : nums) {
            x_or_sum ^= num;
        }
        // Least Significant Bit 最低有效位
        int lsb = (x_or_sum == INT_MIN ? x_or_sum : (x_or_sum & (-x_or_sum)));
        int x1{0};
        int x2{0};
        for (int& num : nums) {
            if (lsb & num) {
                x1 ^= num;
            } else {
                x2 ^= num;
            }
        }
        return {x1, x2};
    }
};
